/*
 *https://leetcode.cn/problems/guess-number-higher-or-lower-ii/
 *375. 猜数字大小 II
 *medium 吴朝泽 2024.10.13
 *区间DP
*/

class Solution {
public:
    int getMoneyAmount(int n) {
        int f[n + 1][n + 1]; // 用于存储从 i 到 j 的最小花费
        memset(f, 0, sizeof(f)); 

        // 从 n-1 到 1 的外层循环，表示当前考虑的起始数字 i
        for (int i = n - 1; i; --i) 
        {
            // 内层循环，表示当前考虑的结束数字 j
            for (int j = i + 1; j <= n; ++j) 
            {
                // 先设定 f[i][j] 的初值为 j + f[i][j - 1]
                // 这里的 j 代表如果直接猜 j，则需要支付 j 的费用，加上处理 i 到 j-1 的费用
                f[i][j] = j + f[i][j - 1]; 

                // 遍历可能的猜测值 k
                for (int k = i; k < j; ++k) 
                {
                    // 更新 f[i][j] 为在当前 k 选择下的最小费用
                    // max(f[i][k - 1], f[k + 1][j]) 是因为我们需要考虑在 k 被猜中后的两种情况
                    // 其中 f[i][k - 1] 是小于 k 的数字的最小费用
                    // f[k + 1][j] 是大于 k 的数字的最小费用
                    f[i][j] = min(f[i][j], max(f[i][k - 1], f[k + 1][j]) + k);
                }
            }
        }
        return f[1][n];
    }
};
